package com.java.comprehensive.arithmetic.leecode.difficulty;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;

public class LeetCode_239 {

	private static class MyQueue {
		static Deque<Integer> queue = new LinkedList<>();

		static void add(Integer value) {
			while (!queue.isEmpty() && value > queue.getLast()) {
				queue.removeLast();
			}
			queue.add(value);
		}

		static void poll(Integer val) {
			if (!queue.isEmpty() && Objects.equals(val, queue.peek())) {
				queue.poll();
			}
		}

		// 队列队顶元素始终为最大值
		static int peek() {
			return queue.peek();
		}
	}

	public static int[] maxSlidingWindow(int[] nums, int k) {

		if (nums.length == 1) {
			return nums;
		}
		int len = nums.length - k + 1;
		// 存放结果元素的数组
		int[] res = new int[len];
		int num = 0;
		// 自定义队列
		MyQueue myQueue = new MyQueue();
		// 先将前k的元素放入队列
		for (int i = 0; i < k; i++) {
			myQueue.add(nums[i]);
		}
		res[num++] = myQueue.peek();
		for (int i = k; i < nums.length; i++) {
			// 滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
			myQueue.poll(nums[i - k]);
			// 滑动窗口加入最后面的元素
			myQueue.add(nums[i]);
			// 记录对应的最大值
			res[num++] = myQueue.peek();
		}
		return res;
	}

	public static void main(String[] args) {
		int[] nums = { -7, -8, 7, 5, 7, 1, 6, 0 };
		System.out.println(Arrays.toString(maxSlidingWindow(nums, 4)));
	}
}
